NC6 二叉树中的最大路径和
import java.util.;


  public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
      this.val = val;
    }
  }
 

public class Solution {
    
      代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     
      
      @param root TreeNode类 
      @return int整型
     

    int max = Integer.MIN_VALUE;
    public int maxPathSum (TreeNode root) {
         write code here
        fun(root);
        return max;
    }

    public int fun(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int l = Math.max(0, fun(root.left));
        int r = Math.max(0, fun(root.right));
        max = Math.max(max, l+r+root.val);
        return root.val + Math.max(l, r);
    }
}